{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Destroy Sequential Targets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: destroyTargets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摧毁一系列目标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数&nbsp;<code>space</code>&nbsp;。</p>\n",
    "\n",
    "<p>你有一台机器可以摧毁目标。给机器 <strong>输入</strong>&nbsp;<code>nums[i]</code>&nbsp;，这台机器会摧毁所有位置在&nbsp;<code>nums[i] + c * space</code>&nbsp;的目标，其中&nbsp;<code>c</code>&nbsp;是任意非负整数。你想摧毁&nbsp;<code>nums</code>&nbsp;中 <strong>尽可能多</strong>&nbsp;的目标。</p>\n",
    "\n",
    "<p>请你返回在摧毁数目最多的前提下，<code>nums[i]</code>&nbsp;的 <strong>最小值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,7,8,1,1,5], space = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。\n",
    "这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。\n",
    "没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,5,2,4,6], space = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>输入 nums[0] 或者 nums[3] 都会摧毁 3 个目标。\n",
    "没有办法摧毁多于 3 个目标。\n",
    "由于 nums[0] 是最小的可以摧毁 3 个目标的整数，所以我们返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [6,2,5], space = 100\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>无论我们输入哪个数字，都只能摧毁 1 个目标。输入的最小整数是 nums[1] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= space &lt;=&nbsp;10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [destroy-sequential-targets](https://leetcode.cn/problems/destroy-sequential-targets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [destroy-sequential-targets](https://leetcode.cn/problems/destroy-sequential-targets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,7,8,1,1,5]\\n2', '[1,3,5,2,4,6]\\n2', '[6,2,5]\\n100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        n_nums = [v % space for v in nums]\n",
    "        c = Counter(n_nums)\n",
    "        max_v = max(c.values())\n",
    "        max_k = {k for k in c if c[k] == max_v}\n",
    "        for n in sorted(nums):\n",
    "            if (n % space) in max_k:\n",
    "                return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        if space == 0 or space == 1:\n",
    "            return nums[0]\n",
    "        from collections import defaultdict\n",
    "        rest = defaultdict(int)\n",
    "        for num in nums:\n",
    "            rest[num%space] += 1\n",
    "        \n",
    "        max_v = -1\n",
    "        res = nums[0]\n",
    "        for num in nums:\n",
    "            cur_v = rest.get(num%space)\n",
    "            if cur_v > max_v:\n",
    "                max_v = cur_v\n",
    "                res = num\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "\n",
    "        for n in nums:\n",
    "            mp[n % space] += 1\n",
    "        \n",
    "\n",
    "        max_ = max(mp.values())\n",
    "\n",
    "        ans = float('inf')\n",
    "        for n in nums:\n",
    "            if mp[n % space] == max_:\n",
    "                ans = min(ans, n)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        mp = Counter()      # space<=1e9，用哈希表可压缩空间\n",
    "        mx = float('-inf')\n",
    "        for num in nums:\n",
    "            mp[num % space] += 1\n",
    "            mx = max(mx, mp[num % space])\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for num in nums:\n",
    "            if mp[num % space] == mx and num < ans:\n",
    "                ans = num\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "        l = [x % space for x in nums]\n",
    "        c = Counter(l)\n",
    "        return nums[l.index(c.most_common(1)[0][0])]\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        # 归一化\n",
    "        c = Counter()\n",
    "        for x in nums:\n",
    "            c[x - x //space*space] += 1\n",
    "        ma = max(c.values())\n",
    "        s = set()  # 所有最大值的归一化\n",
    "        for x in c:\n",
    "            if c[x] == ma:\n",
    "                s.add(x)\n",
    "        mi = inf\n",
    "        for x in nums:\n",
    "            if x - x //space*space in s:\n",
    "                mi = min(mi, x)\n",
    "        return mi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, A: List[int], d: int) -> int:\n",
    "        c = Counter(x % d for x in A)\n",
    "        return min(A, key=lambda x: (-c[x % d], x))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for num in nums:\n",
    "            counter[num % space] += 1 \n",
    "        if not counter:\n",
    "            return 0\n",
    "        maxCnt = counter.most_common(1)[0][1]\n",
    "        res = float('inf')\n",
    "        for num in nums:\n",
    "            if counter[num % space] == maxCnt:\n",
    "                res = min(res, num)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        map = dict()\n",
    "        for n in nums:\n",
    "            if n % space not in map:\n",
    "                map[n % space] = 1\n",
    "            else: map[n % space] += 1\n",
    "\n",
    "        tot, ans = 0, 0x3f3f3f3f\n",
    "        for i in nums:\n",
    "            if tot == map[i % space]:\n",
    "                ans = min(ans, i)\n",
    "            elif tot < map[i % space]:\n",
    "                tot = map[i % space]\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, a: List[int], b: int) -> int:\n",
    "        h=defaultdict(int)\n",
    "        for i in a:\n",
    "            h[i%b]+=1\n",
    "        m=max(h.values())\n",
    "        s={i for i,j in h.items() if j==m}\n",
    "        return min(i for i in a if i%b in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for num in nums:\n",
    "            counter[num % space] += 1 \n",
    "        if not counter:\n",
    "            return 0\n",
    "        maxCnt = counter.most_common(1)[0][1]\n",
    "        res = float('inf')\n",
    "        for num in nums:\n",
    "            if counter[num % space] == maxCnt:\n",
    "                res = min(res, num)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, a: List[int], b: int) -> int:\n",
    "        h=defaultdict(int)\n",
    "        for i in a:\n",
    "            h[i%b]+=1\n",
    "        m=max(h.values())\n",
    "        s={i for i,j in h.items() if j==m}\n",
    "        return min(i for i in a if i%b in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "        l = [x % space for x in nums]\n",
    "        c = Counter(l)\n",
    "        return nums[l.index(c.most_common(1)[0][0])]\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        tmp = defaultdict(int)\n",
    "        for x in nums:\n",
    "            tmp[x % space] += 1\n",
    "        ans = max(tmp.values())\n",
    "        for i in sorted(nums):\n",
    "            if tmp[i % space] == ans:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        nums = sorted(nums)\n",
    "        ans = -1\n",
    "        numofmod = 0\n",
    "        remainder = {}\n",
    "        for num in nums[::-1]: \n",
    "            tmp = num%space\n",
    "            remainder.setdefault(tmp, 0)\n",
    "            remainder[tmp] += 1\n",
    "            if remainder[tmp] >= numofmod: \n",
    "                ans = num\n",
    "                numofmod = remainder[tmp]\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        # 0-space-1之间的数字\n",
    "        # 本题与nums中每个数字与space取余数有关系,同时与第一个取余的起点有关系\n",
    "        nums.sort() # 先排序:便于返回最小值\n",
    "        tmp = [i%space for i in nums]\n",
    "        res = collections.Counter(tmp)\n",
    "        nums.sort(key=lambda x:res[x%space],reverse=True)\n",
    "        print(nums)\n",
    "        #print(nums[tmp.index()])\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        mod_dict = {}\n",
    "        mod_min = {}\n",
    "        for num in nums:\n",
    "            mod = num % space\n",
    "            if mod not in mod_dict.keys():\n",
    "                mod_dict[mod] = 1\n",
    "                mod_min[mod] = num\n",
    "            else:\n",
    "                mod_dict[mod] += 1\n",
    "                if num < mod_min[mod]:\n",
    "                    mod_min[mod] = num\n",
    "\n",
    "        max_mod = -1\n",
    "        max_mod_count = 0\n",
    "        mods = [key for key in mod_dict.keys()]\n",
    "        # mods.sort()\n",
    "        for mod in mods:\n",
    "            if mod_dict[mod] > max_mod_count:\n",
    "                max_mod_count = mod_dict[mod]\n",
    "                max_mod = mod\n",
    "        \n",
    "        min_num = 10 ** 9 + 7\n",
    "        for mod in mods:\n",
    "            if mod_dict[mod] == max_mod_count:\n",
    "                if mod_min[mod] < min_num:\n",
    "                    min_num = mod_min[mod]\n",
    "\n",
    "        return min_num        \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        m = Counter(nums[i] % space for i in range(n))\n",
    "        c = sorted(cnt.keys())\n",
    "        res, ans = 0, 1\n",
    "        for k in c:\n",
    "            t = k % space\n",
    "            if m[t] > res:\n",
    "                res = m[t]\n",
    "                ans = k\n",
    "            m[t] -= 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        dic = defaultdict()\n",
    "        mx = 0\n",
    "        mn = nums[-1]\n",
    "        for i in range(n):\n",
    "            res = nums[i]%space\n",
    "            cnt[res]+=1\n",
    "            if res not in dic.keys():\n",
    "                dic[res]=nums[i]\n",
    "        for k,v in cnt.items():\n",
    "            if v>mx:\n",
    "                mx = v\n",
    "                mn = dic[k]\n",
    "            elif v==mx:\n",
    "                mn = min(mn, dic[k])\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        mod_dict = {}\n",
    "        mod_min = {}\n",
    "        for num in nums:\n",
    "            mod = num % space\n",
    "            if mod not in mod_dict.keys():\n",
    "                mod_dict[mod] = 1\n",
    "                mod_min[mod] = num\n",
    "            else:\n",
    "                mod_dict[mod] += 1\n",
    "                if num < mod_min[mod]:\n",
    "                    mod_min[mod] = num\n",
    "\n",
    "        max_mod = -1\n",
    "        max_mod_count = 0\n",
    "        mods = [key for key in mod_dict.keys()]\n",
    "        # mods.sort()\n",
    "        for mod in mods:\n",
    "            if mod_dict[mod] > max_mod_count:\n",
    "                max_mod_count = mod_dict[mod]\n",
    "                max_mod = mod\n",
    "        \n",
    "        min_num = max(nums)\n",
    "        for mod in mods:\n",
    "            if mod_dict[mod] == max_mod_count:\n",
    "                if mod_min[mod] < min_num:\n",
    "                    min_num = mod_min[mod]\n",
    "\n",
    "        return min_num        \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        f, ans, cur = defaultdict(list), 0, 0\n",
    "        for x in nums:\n",
    "            n = x % space\n",
    "            if n not in f:\n",
    "                f[n] = [0, x]\n",
    "            f[n][0], f[n][1] = f[n][0] + 1, min(f[n][1], x)\n",
    "            if cur < f[n][0]:\n",
    "                cur, ans = f[n][0], f[n][1]\n",
    "            elif cur == f[n][0] and ans > f[n][1]:\n",
    "                ans = f[n][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        \n",
    "        sett=set()\n",
    "        \n",
    "        \n",
    "        dicc=defaultdict(int)\n",
    "        for i in nums:\n",
    "            dicc[i%space]+=1\n",
    "        \n",
    "        ans=inf\n",
    "        maxx=0\n",
    "        \n",
    "        \n",
    "        for i in nums:\n",
    "            if i%space in sett:continue\n",
    "                \n",
    "            if dicc[i%space]>maxx:\n",
    "                ans=i\n",
    "                maxx=dicc[i%space]\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            sett.add(i%space)\n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = dict()\n",
    "        c = t = 0\n",
    "        for x in nums:\n",
    "            y = x % space\n",
    "            if y not in cnt:\n",
    "                cnt[y] = [1, x]\n",
    "            else:\n",
    "                cnt[y][0] += 1\n",
    "                cnt[y][1] = min(cnt[y][1], x)\n",
    "        for c2, t2 in cnt.values():\n",
    "            if (c2 > c or (c2 == c and t > t2)):\n",
    "                c, t = c2, t2\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class help_class():\n",
    "#     def __init__(self, val):\n",
    "#         self.li = [val]\n",
    "#         self.length = 1\n",
    "#         self.min_ = val\n",
    "\n",
    "#     def add_new_val(val):\n",
    "#         self.li.append(val):\n",
    "#         self.length +=1\n",
    "#         self.min_ = min(self.min_, val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "    \n",
    "        nums.sort()\n",
    "        dict1 = {}\n",
    "        \n",
    "        for num in nums:\n",
    "            if num%space not in dict1.keys():\n",
    "                dict1[num%space] = [num]\n",
    "            else:\n",
    "                dict1[num%space].append(num)\n",
    "\n",
    "        x = sorted(dict1, key=lambda k: len(dict1[k]), reverse=True)\n",
    "        return min(dict1[x[0]])\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: list[int], space: int) -> int:\n",
    "        dict1 = {}\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%space not in dict1:\n",
    "                dict1[nums[i]%space]= nums[i]\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=nums[i]%space\n",
    "        c = Counter(nums)\n",
    "        max1= 0\n",
    "        ans = max(nums)\n",
    "        for k,v in c.items():\n",
    "            if v>max1:\n",
    "                ans = dict1[k]\n",
    "                max1 = v\n",
    "            else:\n",
    "                if v==max1:\n",
    "                    ans = min(dict1[k],ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        res = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            res[num % space].append(num)\n",
    "        a, b = 0, 0\n",
    "        for x in res.values():\n",
    "            if len(x) > b:\n",
    "                a = x[0]\n",
    "                b = len(x)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        res = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            res[num % space].append(num)\n",
    "        a, b = 0, 0\n",
    "        for num, x in res.items():\n",
    "            if len(x) > b:\n",
    "                a = x[0]\n",
    "                b = len(x)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = -inf\n",
    "        ans = 0\n",
    "        for a in g.values():\n",
    "            m, low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            m, low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x%space].append(x)\n",
    "        mx=ans=0\n",
    "        for a in g.values():\n",
    "            m=len(a)\n",
    "            low=min(a)\n",
    "            if m>mx or m==mx and low<ans:\n",
    "                mx,ans=m,low\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        res = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            res[num % space].append(num)\n",
    "        a, b = 0, 0\n",
    "        for x in res.values():\n",
    "            if len(x) > b:\n",
    "                a = x[0]\n",
    "                b = len(x)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            g[x % space].append(x)\n",
    "\n",
    "        mx = ans = 0\n",
    "\n",
    "        for a in g.values():\n",
    "\n",
    "            m, low = len(a), min(a)\n",
    "\n",
    "            if m > mx or m == mx and low < ans:\n",
    "\n",
    "                mx, ans = m, low\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        nums.sort()\n",
    "        record = defaultdict(list)\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        max_len = 0\n",
    "\n",
    "        for num in nums:\n",
    "            key = num % space\n",
    "            record[key].append(num)\n",
    "            if len(record[key]) > max_len:\n",
    "                res = record[key][0]\n",
    "                max_len = len(record[key])\n",
    "            elif len(record[key]) == max_len:\n",
    "                res = min(res, record[key][0])\n",
    "        \n",
    "        return res\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        res = defaultdict(list)\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            res[num % space].append(num)\n",
    "        a, b = 0, 0\n",
    "        for x in res.values():\n",
    "            if len(x) > b:\n",
    "                a = x[0]\n",
    "                b = len(x)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)    #按模space相同的数分组\n",
    "        mx = ans = 0\n",
    "        for a in g.values():          #遍历不同的组\n",
    "            m, low = len(a), min(a)   #m为每个组的长度用于比较，low为组里最小的数，用于输出\n",
    "            if m > mx or (m==mx and low<ans):\n",
    "                mx, ans = m, low\n",
    "        return ans\n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            m,low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            m, low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        # 模space相同的数是可以被这些数种最小的数摧毁，\n",
    "        # 按模space的结果分组，最大组的最小值\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            m, low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        mdict=defaultdict(list)\n",
    "        for i in nums:\n",
    "            mdict[i%space].append(i)\n",
    "        mx,ans=0,max(nums)\n",
    "        for i in mdict.values():\n",
    "            if len(i)>mx or mx==len(i) and min(i)<=ans:\n",
    "                mx=len(i)\n",
    "                ans=min(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        cnt = defaultdict(list)\n",
    "        for num in nums:\n",
    "            cnt[num%space].append(num)\n",
    "        \n",
    "        ans = inf\n",
    "        res = -1\n",
    "        for num in cnt:\n",
    "            low = min(cnt[num])\n",
    "            if len(cnt[num]) > res or (len(cnt[num]) == res and low < ans):\n",
    "                ans = low\n",
    "                res= len(cnt[num])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx, ans = 0, inf\n",
    "        for a in g.values():\n",
    "            if len(a) > mx or (len(a) == mx and min(a) < ans):\n",
    "                mx, ans = len(a), min(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            m, low = len(a), min(a)\n",
    "            if m > mx or m == mx and low < ans:\n",
    "                mx, ans = m, low\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x%space].append(x)\n",
    "        mx=ans=0\n",
    "        for a in g.values():\n",
    "            m,low=len(a),min(a)\n",
    "            if m>mx or m==mx and low<ans:\n",
    "                mx,ans=m,low\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\r\n",
    "        d = defaultdict(list)\r\n",
    "        for x in nums:\r\n",
    "            d[x % space].append(x)\r\n",
    "        #d中list的长度最大值\r\n",
    "        max_len = max(len(d[k]) for k in d)\r\n",
    "        ans = float('inf')\r\n",
    "        for k in d:\r\n",
    "            if len(d[k]) == max_len:\r\n",
    "                ans = min(ans, min(d[k]))\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        \n",
    "        mx = ans = 0\n",
    "        for a in g.values():\n",
    "            n, mn = len(a), min(a)\n",
    "            if n > mx or n == mx and mn < ans:\n",
    "                mx, ans = n, mn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x%space].append(x)\n",
    "        mx=ans=0\n",
    "        for a in g.values():\n",
    "            m,low=len(a),min(a)\n",
    "            if m>mx or m==mx and low<ans:\n",
    "                mx,ans=m,low\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        # 按摸分组\n",
    "        group = defaultdict(list)\n",
    "        for num in nums:\n",
    "            group[num % space].append(num)\n",
    "        max_nums = 0\n",
    "        min_value = float('inf')\n",
    "\n",
    "\n",
    "        for k,v in group.items():\n",
    "            if(len(v) >= max_nums):\n",
    "                if len(v) > max_nums:\n",
    "                    min_value = min(v)\n",
    "                else:\n",
    "                    min_value = min(min_value, min(v))\n",
    "                max_nums = len(v)\n",
    "        \n",
    "        return min_value\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x%space].append(x)\n",
    "        mx=ans=0\n",
    "        for a in g.values():\n",
    "            length=len(a)\n",
    "            low=min(a)\n",
    "            if length>mx or (length==mx and low<ans):\n",
    "                ans=low\n",
    "                mx=length\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        dct = defaultdict(list)\n",
    "        for x in nums:\n",
    "            dct[x % space].append(x)\n",
    "        dct1 = sorted(dct.items(), key=lambda i: -len(i[1]))\n",
    "        ans = min(dct1[0][1])\n",
    "        t = len(dct1[0][1])\n",
    "        for x, y in dct1:\n",
    "            if len(y) != t:\n",
    "                break\n",
    "            ans = min(ans, min(y))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destroyTargets(self, nums: List[int], space: int) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x % space].append(x)\n",
    "        print(g)\n",
    "        max_len = 0\n",
    "        min_x = 0\n",
    "        for i in g.values():\n",
    "            m = len(i)\n",
    "            low = min(i)\n",
    "            if m > max_len:\n",
    "                max_len = m\n",
    "                min_x = low\n",
    "            if m == max_len and min_x > low:\n",
    "                min_x = low\n",
    "        return min_x"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
